#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: fib.py 
@version:
@time: 2023/12/16 
"""


class Fib:
    def func1(self, n):
        """
        递归算法，自顶向下看，要计算fib(5)就要先计算fib(4)和fib(3)，依次向下推算；
        由计算过程可见，fib(3)、fib(2)、fib(1)被计算了多次，在i=5的情况下已经有如此多重复计算，随着i进一步增大，
        重复计算量会急剧增大，导致时间复杂度极大，运行效率低下。其时间复杂度为O(n^2)
                fib(5)
                /  \
            fib(3) fib(4)
        /  \       /   \
    fib(2) fib(1) fib(3)  fib(2)
                /   \
             fib(1) fib(2)

        :param n:
        :return:
        """
        if n < 1:
            return 0
        if n < 3:
            return 1
        return self.func1(n - 1) + self.func1(n - 2)

    @staticmethod
    def func2(n):
        """
        采用动态规划算法，即自底向上看，fib(5)把fib(1)~fib(4)提前计算并保存起来，就可以避免递归中的重复计算，
        降低时间复杂度。由于要保存fib(1)~fib(4)需要额外的内存空间，空间复杂度会相对较高，
        因此动态规划算法是一种用较高空间复杂度换取较低的时间复杂度的算法，时间复杂度为O(n)。

        l: l变量用列表l来保存n以前的fib(1)~fib(n-1)的值，因此需要额外的长度为n的内存单元。
        :param n:
        :return:
        """
        l = [0, 1, 1]
        for i in range(3, n + 1):
            l.append(l[i - 1] + l[i - 2])
        return l[n]

    @staticmethod
    def func3(n):
        """
        进一步优化，也可以不保存n以前的斐波那契数列，而是用3个变量保存当前计算到的斐波那契，
        可以实现空间复杂度为O(1)，时间复杂度为O(n)的既节省内存又高效的算法。

        用python实现改进后的动态规划算法：
        1. a变量：用于保存fib(n-2)的值
        2. b变量：用于保存fib(n-1)的值。
        3. c变量：用于保存fib(n-1)+fib(n-2)的值

        在fib(5)的实现过程中，相当于变量a、b、c不断同时向后移动，无须将数据全部保存起来。

        step1     1   1   2
                  |   |   |
        step1     1   1   2   3
                      |   |   |
        step3     1   1   2   3   5
                          |   |   |
                          a   b   c
        :param n:
        :return:
        """
        a = b = 1
        c = None
        for i in range(3, n + 1):
            c = a + b
            a = b
            b = c
        return c


class TestFib(Fib):
    def test_func1(self):
        res = self.func1(20)
        print(res)

    def test_func2(self):
        res = self.func2(20)
        print(res)

    def test_func3(self):
        res = self.func3(20)
        print(res)


"""
总结：
### 1. 最优子结构：fib(5)的计算和fib(4)的计算问题一致，具有最优子结构

### 2. 重叠子问题：计算过程存在重复计算

### 3. 状态与状态转移方程：当i>=3时，f(i) = f(i-1)+f(i-2) 

### 4. 边界条件：i<1时，return 0,i<3时，return 1

"""
